Exemplary embodiments of the invention relate to methods of processing 3D sensor data generated by systems such as radar or lidar systems, and to computer programs for carrying out such methods.
3D sensor data from radar, lidar and similar systems is increasingly becoming the main source of data for both manned and unmanned vehicles operating in demanding environments, particularly in degraded visual environments. Such systems are an important tool for assessing terrain in order to establish clear pathways for ground-based vehicles and landing areas for aircraft, especially vertically-landing aircraft. The segmentation of 3D sensor data gathered by such a system in order to distinguish ground returns from returns corresponding to elevated objects is typically a first processing step that is carried out immediately after basic filtering. Even in situations where measurement of terrain is not a goal in itself, processing 3D sensor data to segment ground and elevated objects is important for reasons of runtime optimization and classification stability. In the case of a manned vehicle, the processing of 3D sensor data is carried out in real time within a synthetic vision system to provide segmentation, and the results are visualized in some way to a pilot or driver. In the case of a fully autonomous vehicle, the processing of 3D sensor data replaces all evaluation tasks normally carried out by a pilot or driver, so that the speed and reliability with which the 3D data is processed to provide segmentation is of crucial importance to the overall performance of the vehicle.
In one known approach to terrain segmentation, the height value of a given return in a 3D data set is compared to those of neighboring returns and ground segmentation is carried out assuming that returns corresponding to ground areas show the most linear variation in height values. (See for example “A Self-Supervised Terrain Roughness Estimator for Off-Road Automous Driving”, D. Stavens and S. Thrun, Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence, MIT, Cambridge, Mass., USA, 2006.) This approach has the disadvantage that certain terrain features, such as forest canopies, which also produce returns having a roughly linear variation in height value, may be erroneously classified as ground returns.
Other methods for ground segmentation involve plane-fitting techniques within neighborhoods of returns to determine surface roughness in 3D. A surface is fitted to a neighborhood (cell) of returns and the surface normal of the cell is determined. A ground region is identified if the surface normals of adjacent cells have a smoothness greater than a certain threshold value. Plane-fitting techniques may also result in the erroneous classification of ground regions if the height values of adjacent cells are all elevated.
More reliable ground segmentation may be achieved, but at the expense of increased computational effort. For example, Fourier analysis for the identification of spectral similarities in returns may be used in combination with plane-fitting (see for example “Terrain Roughness Measurement from Elevation Maps”, R. Hoffman and E. Krotov, SPIE, Volume 1195, Mobile Robots IV, 1989.) A course-fine approach for estimating terrain slope and roughness is described by S. Scherer, in “Low-Altitude Operation of Unmanned Rotorcraft”, PhD thesis, Carnegie Mellon University, Pittsburgh, 2011. Cells comprising groups of returns for which the standard deviation of height value exceeds a threshold are classified as corresponding to elevated objects.
A further disadvantage of these prior art methods is that they require a significant difference between the height value of a given return and that of a ground return in order for it to be classified as corresponding to an elevated object. For practical sensors having limited range resolution and beam divergence, sufficient height differences in the 3D data are not always achievable.
The present invention provides a method of processing 3D sensor data to provide terrain segmentation, the 3D sensor data comprising a respective coordinate set for each of a series of returns detected by a 3D sensor positioned above the terrain by scanning the 3D sensor over the terrain in a known smooth, analytical scan pattern, each coordinate set corresponding to a position vector with respect to the 3D sensor of a point in the terrain giving rise to a respective return and the coordinates defining a horizontal plane. The method comprises processing the 3D data by the steps of:
(i) identifying a series of returns having positions in the horizontal plane that would lie on a substantially smooth path or scan line in the horizontal plane in the case of returns from an idealized flat terrain and the known analytical scan pattern; and
(ii) processing the horizontal coordinates of the returns in order to identify returns having positions in the horizontal plane deviating by more than a pre-determined extent from positions of returns from a hypothetical perfect plane and classifying the deviating returns as non-ground returns corresponding to elevated objects in the terrain, thereby differentiating non-ground returns from ground returns.
By analyzing the positions of returns in the horizontal plane so as to detect deviations in those positions from the positions in the horizontal plane expected of corresponding returns from an ideal flat terrain using the known 3D sensor scan pattern, elevated objects in the terrain may be identified and segmented from ground regions in the terrain without the need for processing data corresponding to the height values of the returns. This allows for faster data processing for a given amount of processing resources, or equivalently it allows for a reduced amount of processing resources for a given amount of processing time. The prior art methods have the disadvantage that they require a high level of processing resources resulting from the need to directly process 3D sensor data in real time. In the case of a high-resolution 3D data set, it may be necessary to process more than 10,000 data points per second in a practical segmentation system. The invention takes advantage of the fact that for a known analytical scan pattern of a 3D sensor, a set of returns that will correspond to an identifiable smooth path or scan line comprising a series of consecutive positions in the horizontal plane, in the case of an idealized flat terrain, is readily identifiable a priori, whereas in prior art techniques this identification requires additional processing effort. This means that in a method of the invention the processing burden needed to provide segmentation of the 3D sensor data increases only linearly with the amount of data (i.e. the number of returns), whereas in the prior art the processing effort increases with the square of the number of returns, since each return has to be compared to every other return in the data in order to identify sets of returns corresponding to a smooth paths or scanlines in the horizontal plane.
The invention also has the advantage that objects that are smaller in size than the range-resolution of the 3D sensor may be identified, as well as objects smaller in extent than the distance between adjacent scan lines in the horizontal plane. By analyzing the positions of returns in the horizontal plane, the method is less susceptible to the erroneous classification of extended elevated areas, such a forest canopies, as ground areas in a terrain.
Preferably, the method further comprises the steps of:
(i) identifying one or more further series of returns, each series comprising returns that would lie on a respective substantially smooth path or scan line in the horizontal plane in the case of returns from an idealized flat terrain and the known analytical scan pattern,(ii) processing the horizontal coordinates of the returns in each series to identify returns having positions in the horizontal plane that deviate by more than a pre-determined extent from the corresponding substantially smooth path or scan line, and(iii) classifying returns found in step (ii) as non-ground returns corresponding to elevated objects in the terrain, thereby providing full terrain segmentation of the 3D sensor data.
In this way the entire 3D sensor data may be analyzed and segmented into ground areas and elevated objects (corresponding to ground and non-ground returns) by analyzing the positions in the horizontal plane of all returns corresponding to the 3D sensor data, and comparing these positions to those expected of returns from an ideal flat terrain scanned by the known analytical scan pattern.
The step of processing the horizontal coordinates of returns in a given series in order to identify returns having positions in the horizontal plane deviating by more than a pre-determined extent from the corresponding substantially smooth path or scan line is conveniently carried out by the steps of:
(i) evaluating the distances in the horizontal plane between pairs of adjacent returns in the series;
(ii) classifying a return as corresponding to a non-ground return from an elevated object in the terrain if the distance of the return from a neighboring return in the series exceeds a pre-determined threshold value.
This provides a rapid method of identifying returns corresponding to elevated objects as only in the distances in the horizontal plane between adjacent pairs of returns need be calculated.
Alternatively, the step of processing the horizontal coordinates of returns in a given series in order to identify returns having positions in the horizontal plane deviating from the corresponding substantially smooth path or scan line by more than a pre-determined extent may be carried out by the steps of:
(i) calculating an average path in the horizontal plane based on the positions of the returns in the horizontal plane, and
(ii) identifying a given return in the series as corresponding to a return from an elevated object in the terrain if its distance from the average path exceeds a pre-determined threshold value.
The step of processing the horizontal coordinates of returns in a given series in order to identify returns having positions in the horizontal plane deviating from the corresponding substantially smooth path or scan line by more than a pre-determined extent may also be carried out by the steps of:
(i) for a return under consideration, evaluating the angle in the horizontal plane between straight lines connecting the return to respective adjacent returns in the series, and
(ii) classifying said return as a return from an elevated object in the terrain if the angle is less than a pre-determined threshold value.
Preferably, for a given set of returns, the returns are considered sequentially in order of horizontal position for correspondence to a non-ground return from an elevated object, and wherein, upon detection of a non-ground return in the set, the method further comprises the steps of:
(i) identifying the next return in the set that is subsequent in horizontal position in the set to that return and which corresponds to a ground return;
(ii) for each return in the set intermediate in horizontal position between that of the non-ground return and that of the ground return identified in step (i), evaluating the distance in the horizontal plane between that return and an adjacent scanline; and(iii) where said distance is less than a pre-determined threshold value, classifying the corresponding return as a non-ground return from an elevated object.
This ensures that in the case of an elevated object that is extended in the horizontal plane, a series of returns from the object is not erroneously classified as a series of ground returns because they have similar positions in the horizontal plane. If a non-ground return is identified, then the distances in the horizontal plane of subsequent returns are each examined for their proximities to the positions of ground returns corresponding to an adjacent scan line, and any such subsequent return is classified as corresponding to the extended elevated object if the corresponding proximity is below a pre-determined threshold value. The examination of returns subsequent to the initially identified non-ground return ceases once a subsequent ground return in the set is identified.
The method may further comprise the subsequent steps of:
(i) mapping returns classified as ground returns and non-ground returns to an array of corresponding ground and non-ground pixels, a pixel being classified as a ground pixel in the absence of a corresponding return;
(ii) identifying any ground pixel that is adjacent in the horizontal plane to a non-ground pixel;
(iii) for each pixel identified in step (ii), evaluating the difference between its height value and that of the adjacent non-ground pixel;
(iv) for each pixel identified in step (ii), evaluating the difference between its height value and that of the lowest ground pixel in the 3D data; and
(v) re-classifying a pixel identified in step (i) as a non-ground pixel if the difference found in step (iii) is less than the difference found in step (iv).
This allows for returns in the 3D data to be converted into a corresponding array of pixels each of which is classified as a ground or non-ground pixel, while providing for the re-classifying of a ground pixel as a non-ground pixel if it has a height value closer to that of a neighboring non-ground pixel than to the ground pixel having the lowest height value. This avoids the erroneous classification of a pixel as a ground pixel in the case where the pixel has initially been classified as a ground pixel due to the absence of a corresponding return from the terrain. The absence of a return from a part of the terrain may, for example, result from the absorption of some or all of the energy of a return by some obscurant between the terrain and the 3D sensor, or the mirroring-away of energy incident on a part of the terrain by the presence of water, ice etc.
The difference between the position in the horizontal plane of a ground return and a non-ground return corresponding to position vectors of the same elevation (i.e. inclination to the horizontal plane) is greater than the height at which the non-ground return is reflected, provided the viewing angle is less than 45 degrees. Therefore, the 3D data preferably corresponds to returns from the terrain corresponding to position vectors having a viewing angle which is less than 45 degrees, in order to provide increased sensitivity of detection for elevated objects.
Preferably, the 3D sensor data is pre-processed in order to remove artifacts prior to the comparison in order to reduce the likelihood of incorrect segmentation for parts of the terrain as a result of the presence of such artifacts.
Advantageously, the 3D sensor data is pre-processed to limit potential terrain measurements by taking into account only the final measured distance in the case of multiple returns from a single position in the terrain.
Further aspects of the invention provide a computer program for carrying out the method of the invention, a computer program product storing such a computer program and a computer programmed with such a computer program.